#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<limits.h>

typedef struct DoubleListNode
{
    int val;
    struct DoubleListNode *next, *prev;
}DoubleListNode;
/*双向节点构造*/
DoubleListNode *newDoubleListNode(int val)
{
    DoubleListNode *p = (DoubleListNode *)malloc(sizeof(DoubleListNode));
    p->val = val;
    p->next = p->prev = NULL;
    return p;
}

typedef struct 
{
    int size;
    DoubleListNode *front, *rear;
}Deque;
/*Deque构造*/
Deque *newDeque()
{
    Deque *p = (Deque *)malloc(sizeof(Deque));
    p->size=0;
    p->front = NULL;
    p->rear = NULL;
    return p;
}
/*Deque析构*/
void delDeque(Deque *p)
{
    while (p->front)
    {
        DoubleListNode *node = p->front;
        p->front = p->front->next;
        free(node);
    }
    free(p);
}
/*获取长度*/
int size(Deque *q)
{
    return q->size;
}
/*是否为空*/
bool isEmpty(Deque *q)
{
    return q->size == 0;
}
/*将元素添加至队首*/
void push_first(Deque *q, int val)
{
    DoubleListNode *node = newDoubleListNode(val);
    if (q->size == 0)
    {
        q->front = node;
        q->rear = node;
        q->size++;
        return;
    }
    node->next = q->front;
    q->front->prev = node;
    q->front = node;
    q->size++;
}
/*将元素添加至队尾 */
void push_last(Deque *q, int val)
{
    DoubleListNode *node = newDoubleListNode(val);
    if (q->size == 0)
    {
        q->front = node;
        q->rear = node;
        q->size++;
        return;
    }
    node->prev = q->rear;
    q->rear->next = node;
    q->rear = node;
    q->size++;
}
/*访问队首元素*/
int peek_first(Deque *q)
{
    if (q->size == 0)
    {
        printf("双向队列为空\n");
        return INT_MAX;
    }
    return q->front->val;
}
/*访问队尾元素*/
int peek_last(Deque *q)
{
    if (q->size == 0)
    {
        printf("双向队列为空\n");
        return INT_MAX;
    }
    return q->rear->val;
}
/*删除队首元素*/
int pop_first(Deque *q)
{
    int val = peek_first(q);
    DoubleListNode *node = q->front;
    q->front = q->front->next;
    q->front->prev = NULL;
    free(node);

    q->size--;
    return val;
}
/*删除队尾元素*/
int pop_last(Deque *q)
{
    int val = peek_last(q);
    DoubleListNode *node = q->rear;
    q->rear = q->rear->prev;
    q->rear->next = NULL;
    free(node);

    q->size--;
    return val;
}
/*打印队列*/
void printDeque(Deque *q)
{
    DoubleListNode *node = q->front;
    while (node != NULL)
    {
        printf("%d ", node->val);
        node = node->next;
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    // 初始化1 3 2 5 4 
    Deque *queue = newDeque();
    push_first(queue, 4);
    push_first(queue, 5);
    push_first(queue, 2);
    push_first(queue, 3);
    push_first(queue, 1);
    printDeque(queue);

    // 队首，队尾
    printf("上面的队首:%d,队尾:%d\n", peek_first(queue), peek_last(queue));
    // 队首出队
    int val;
    val = pop_first(queue);
    printf("队首出队:");
    printDeque(queue);
    printf("上面的队首:%d,队尾:%d\n", peek_first(queue), peek_last(queue));
    // 队尾出队
    val = pop_last(queue);
    printf("队尾出队:");
    printDeque(queue);
    printf("上面的队首:%d,队尾:%d\n", peek_first(queue), peek_last(queue));

    // 队尾入队
    push_last(queue, 999);
    printf("队尾入队:");
    printDeque(queue);
    printf("上面的队首:%d,队尾:%d\n", peek_first(queue), peek_last(queue));

    // 析构
    delDeque(queue);
    return 0;
}
